package offer;

/**
 * @author ZhanBo
 * @date 2020/7/11
 */
public class Solution51 {

    public static void main(String[] args) {
        int [] array = {7,5,6,4};
        System.out.println(reversePairs(array));

    }


    /**
     * 剑指 Offer 51. 数组中的逆序对
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
     * 输入: [7,5,6,4]
     * 输出: 5
     * @param nums
     * @return
     */
    public static int reversePairs(int[] nums) {
        int result = 0;
        if (nums==null || nums.length == 1){
            return result;
        }
        int beforeIndex = 0 ;
        int afterIndex = nums.length-1;
        for (int i = 0 ; i < nums.length ; i++){
            while (beforeIndex != afterIndex && beforeIndex<nums.length-1 && afterIndex<=nums.length-1){
                if (nums[beforeIndex] > nums[afterIndex]){
                    result++;
                }
                afterIndex--;
            }
            beforeIndex++;
            afterIndex=nums.length-1;
        }
        return result;
    }


    /****************************/

    public int result = 0;

    public int reversePairs2(int[] nums) {
        if(nums == null || nums.length == 1) {
            return 0;
        }
        mergeCount(nums,0,nums.length-1);
        return result;
    }

    public void mergeCount(int[] nums, int left, int right){
        if(nums.length < 2 || nums == null || left == right) {
            return ;
        }
        int mid = left + (right-left)/2;
        mergeCount(nums,left,mid);
        mergeCount(nums,mid+1,right);
        merge(nums,left,mid,right);

    }

    public void merge(int[] nums,int left, int mid, int right){
        int[] help = new int[right-left+1];
        int p = help.length-1;
        int temp = mid+1;
        while(mid >= left && right >= temp){
            //记录下当前两个有序数组中的逆序对个数
            result = nums[mid] > nums[right] ? result+right-temp+1 : result;
            help[p--] = nums[mid] > nums[right] ? nums[mid--] : nums[right--];
        }
        while(mid >= left) {
            help[p--] = nums[mid--];
        }
        while(right >= temp) {
            help[p--] = nums[right--];
        }
        for(int i = 0; i<help.length; i++) {
            nums[left+i] = help[i];
        }
    }

}
